1667B - Optimal Partition - CodeForces Solution

import io,os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


class segment_max(object):

 
        def merge(self,num,minimum):
        return max(minimum,num)


    def __init__(self,n):
        self.n = n
        self.arr = [-2147483647]*(2*n)




    def update(self,index,target):

        if self.arr[index] >= target:
            return 

        self.arr[index] = target
        if index & 1:
            nexttarget = self.merge( self.arr[index], self.arr[index-1])
        else:
            nexttarget = self.merge( self.arr[index], self.arr[index+1])
        if index>0:  self.update(index>>1,nexttarget )


    def addnum(self,index,diff):
        self.update(index+self.n, self.arr[index+self.n] + diff)


    def query(self,left,right):
        i,j = self.n+left,  self.n+right+1
        output = -2147483648  
        while i<j:
            if i&1:
                output = self.merge(self.arr[i],output)
                i += 1
            if j&1:
                j -= 1
                output = self.merge(self.arr[j],output)
            i = i >> 1
            j = j >> 1
        return output





def main(t):


    n = int(input())
    arr = list(map(int,input().split()))
    accu = [0]*(n+1)
    for i in range(n):
        accu[i] = accu[i-1] + arr[i]
    temp = []
    for i in range(n):
        temp.append((accu[i],i))
    temp.append((0,-1))
    temp.sort()
    cor = {}
    index = 0
    for [accunum,i] in temp:
        if str(accunum) not in cor:  
            cor[str(accunum)] = index
            index += 1

    


    seg_min = segment_max(n+1)
    seg_max = segment_max(n+1)
    index = cor[str(0)]

    seg_min.update(index+n+1,1)
    seg_max.update(index+n+1,-1)

    maxdp = {}
    curr = 0
    maxdp[str(curr)] = 0


    for i in range(n):
        index = cor[str(accu[i])]
        num1 = seg_min.query(0,index-1) + i
        num2 = seg_max.query(index+1,n) - i
        if str(accu[i]) in maxdp:  
            num3 = maxdp[str(accu[i])]
        else:  num3 = -2147483648

 
        num = max(num1,num2,num3)
        if str(accu[i]) in maxdp:  
            maxdp[str(accu[i])] = max(maxdp[str(accu[i])],num)
        else:
            maxdp[str(accu[i])] = num

        seg_min.update(index+n+1, num-i )
        seg_max.update(index+n+1, num+i )

    print(num)    

        
        
        






























T = int(input())
t = 1
while t<=T:
    main(t)
    t += 1